//#include <stdio.h>
//
//void Swap(int* px, int* py)
//{
//    int tmp = *px;
//    *px = *py;
//    *py = tmp;
//}
//
//void justDown(int arr[], int sz, int father_idx)
//{
//    int child_idx = father_idx * 2 + 1; // 计算出左孩子的值（默认认为左孩子大）
//    while (child_idx < sz) // 最坏情況：调到叶子（child_idx >= 数组范围时必然已经调到叶子）
//    {
//        if ((child_idx + 1 < sz) && (arr[child_idx + 1] < arr[child_idx]))
//        {   // 如果右孩子存在且右孩子比左孩子小
//            child_idx = child_idx + 1;// 让其代表右孩子
//        }
//        if (arr[child_idx] < arr[father_idx])//如果孩子的值小于父亲的值（不符合小堆的性质）
//        {
//            Swap(&arr[child_idx], &arr[father_idx]);
//            father_idx = child_idx;          // 更新下标往下走
//            child_idx = father_idx * 2 + 1;  // 计算出该节点路线的新父亲
//        }
//        else // 如果孩子的值大于父亲的值（符合小堆的性质）
//        {
//            break;
//        }
//    }
//}
//
//
//完整堆排序_降序
//void HeapSort(int arr[], int sz)
//{
//    创建小堆，选出最小的数，时间：O(N)
//    int father = ((sz - 1) - 1) / 2;  // 计算出最后一个叶子节点的父亲
//    while (father >= 0)
//    {
//        justDown(arr, sz, father);
//        father--;
//    }
//
//    交换后调堆  时间：O(N * logN)
//    int end = sz - 1;
//    while (end > 0)
//    {
//        Swap(&arr[0], &arr[end]);
//        justDown(arr, end, 0);
//        end--;
//    }
//}
//
//void PrintArray(int arr[], int sz)
//{
//    for (int i = 0; i < sz; i++)
//    {
//        printf("%d ", arr[i]);
//    }
//    printf("\n");
//}
//
//int main()
//{
//    int arr[] = { 70, 56, 30, 25, 15, 10, 75 };
//    int sz = sizeof(arr) / sizeof(arr[0]);
//
//    printf("排序前: ");
//    PrintArray(arr, sz);
//
//    HeapSort(arr, sz);
//
//    printf("排序后: ");
//    PrintArray(arr, sz);
//
//    return 0;
//}
//
#include <stdio.h>

void Swap(int* px, int* py)
{
    int tmp = *px;
    *px = *py;
    *py = tmp;
}

//void justDown(int arr[], int sz, int father_idx)
//{
//    int child_idx = father_idx * 2 + 1; // 计算出左孩子的值（默认认为左孩子大）
//    while (child_idx < sz) // 最坏情況：调到叶子（child_idx >= 数组范围时必然已经调到叶子）
//    {
//        if ((child_idx + 1 < sz) && (arr[child_idx + 1] > arr[child_idx]))
//        {   // 如果右孩子存在且右孩子比左孩子大
//            child_idx = child_idx + 1;// 让其代表右孩子
//        }
//        if (arr[child_idx] > arr[father_idx])//如果孩子的值大于父亲的值（不符合大堆的性质）
//        {
//            Swap(&arr[child_idx], &arr[father_idx]);
//            father_idx = child_idx;          // 更新下标往下走
//            child_idx = father_idx * 2 + 1;  // 计算出该节点路线的新父亲
//        }
//        else // 如果孩子的值小于父亲的值（符合大堆的性质）
//        {
//            break;
//        }
//    }
//}
void justDown(int* arr, int n, int root)//大堆下调
{
    int father = root;
    int child = father * 2 + 1;//默认左孩子大
    while (child < n)
    {
        if (child + 1 < n && arr[child] < arr[child + 1]) // 如果右孩子存在且右孩子比左孩子大
        { 
            child++;
        }
        if (arr[father] < arr[child])
        {
            int tmp = arr[father];
            arr[father] = arr[child];
            arr[child] = tmp;

            father = child;
            child = father * 2 + 1;
        }
        else
        {
            break;
        }
    }
}
//完整堆排序_升序
void HeapSort(int arr[], int sz)
{
    //创建大堆，选出最大的数，时间：O(N)
    int father = ((sz - 1) - 1) / 2;  // 计算出最后一个叶子节点的父亲
    while (father >= 0)
    {
        justDown(arr, sz, father);
        father--;
    }

    //交换后调堆  时间：O(N * logN)
    int end = sz - 1;
    while (end > 0)
    {
        Swap(&arr[0], &arr[end]);
        justDown(arr, end, 0);
        end--;
    }
}

void PrintArray(int arr[], int sz)
{
    for (int i = 0; i < sz; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main()
{
    int arr[] = { 70, 56, 30, 0 ,-555, 25, 15, 10,-7, 845 ,56466, 75 };
    int sz = sizeof(arr) / sizeof(arr[0]);

    printf("排序前: ");
    PrintArray(arr, sz);

    HeapSort(arr, sz);

    printf("排序后: ");
    PrintArray(arr, sz);

    return 0;
}